package com.lyy;

import org.junit.Test;

import java.util.Arrays;

public class PaiXu {
     int[] array={7,5,4,6,2,1};



    /**
     * 冒泡排序,假设按升序排列，
     * 外层循环控制排序的趟数，内层循环依次比较大小并交换前后两个元素，第一趟完成后最大的数已经在最右边，
     * 第二趟排序时，内层循环次数减一，把第二大的数放在倒数第二位
     * 依次类推，第三趟结束后第三大的数会在倒数第三位的位置...
     * 优化：如果内层的依次循环后没有进行交换，说明数组已经有序了，外层就不需要继续循环趟数，可以直接跳出循环，结束排序
     * 需要n-1趟
     */
    @Test
    public  void bubbleSort(){
        for (int i = 0; i < array.length; i++) {
            boolean isChange=false;//内层是否进行交换的标记
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    int temp=0;
                    temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    isChange=true;//交换标记改为进行交换
                }
            }
            if(!isChange){
                //如果内层没有交换，说明数组已经有序
                break;
            }
        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * 选择排序，假设按升序排列,(选择的意思是内层循环选择出“最大”的值)
     * 外层循环控制循环的趟数，第一趟排序，内层循环找到数组的最大值，然后外层和最后一位交换，完成后，最大值在右边，
     * 第二趟时，内循环找到数组第二大的值，在外层和倒数第二位交换，完后后倒数第二位为第二大的数，
     * 依次类推，内层循环次数每次都会减一，外层循环每次交换的位置也会向左走一位
     * 需要排序n-1趟
     */
    @Test
    public void selectionSort(){
        for (int i = 0; i < array.length-1; i++) {
            int maxIndex=0;//最大值的角标
            for (int j=0;j<array.length-i;j++){
                if(array[j]>array[maxIndex]){
                    maxIndex=j;
                }
            }
            //把当前趟的"最大值"所在的位置 和“最后”一位交换
            int temp=array[maxIndex];
            array[maxIndex]=array[array.length-1-i];
            array[array.length-1-i]=temp;
        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * 假设是由小到大排序,插入的意思是把一个数插入到一个已经有序的数组中
     * 插入排序：第一次把数组的第0号元素当做有序，把第1号元素插入这个有序集中,
     * 第二次把数组的第2号元素插入由0号和1号组成的有序数组中。
     * 每次插入的原理：
     * 准备一个空位来存放新元素,刚开始=新插入元素所在的位置,倒叙遍历有序数组,如果当前元素大于待排序元素,就把其向右移一位,空位
     * 向左移一位,内层一趟循环结束后把新元素放到最终空位上
     */
    @Test
    public void insertSort2(){
        for (int i = 1; i < array.length; i++) {
            int currentElement=array[i];//保存当前元素
            int pos=i;//一个空位,用来给有序数组插入新的元素
            //内层循环倒叙遍历已经有序的数组
            for(int j=i-1;j>=0;j--){
                //如果该元素比当前待排序元素大，就把其向右移动一位，空出新的空位 6,7,8<----1
                if(array[j]>currentElement){
                    array[pos]=array[j];
                    pos--;//空位向左移动一位
                }
            }
            //内层循环完后就会找到合适的空位
            array[pos]=currentElement;
        }

        System.out.println(Arrays.toString(array));
    }

    //其他排序方式：快速排序，归并排序

    /**
     * 合并两个有序数组的方法,归并算法
     * @param data
     * @param start
     * @param end
     */
    public static void merge(int[] data,int start,int end){
        int[] tempArray=new int[data.length];
        int mid=(start+end)/2;
        int p1=start;//检测指针1,子序列1
        int p2=mid+1;//检测指针2,子序列2
        int p3=start;//临时存储数组的检测指针
        while ( p1<=mid && p2<=end ){
            if(data[p1]>data[p2]){
                tempArray[p3]=data[p2];
                p2++;
                p3++;
            }else{
                tempArray[p3]=data[p1];
                p1++;
                p3++;
            }
        }

        //子序列1或2中没有遍历到的元素直接续在tempArray的后边
        while (p1<=mid){
            tempArray[p3]=data[p1];
            p3++;
            p1++;
        }
        while (p2<=end){
            tempArray[p3]=data[p2];
            p3++;
            p2++;
        }
        //这两个while不可能同时成立

        //把tempArray赋值给data中对应的位置
        for (int i = start; i <= end; i++) {
            data[i]=tempArray[i];
        }
    }

    //测试合并两个有序数组的方法
    @Test
    public void mergeTest(){
        int[] data={3,4,6,1,2,3};
        merge(data,0,5);
        System.out.println(Arrays.toString(data));
    }

    /* 归并排序:把数组不停的划分为子数组，当子数组只剩下一个元素时它就是有序的
    * 然后再把这些子数组用归并算法合并成新数组
    * */
    public static void mergeSort(int[] data,int start,int end){
        if (start<end){
            int mid=(start+end)/2;
            //排左办部分
            mergeSort(data,start,mid);
            //排右半部分
            mergeSort(data,mid+1,end);
            //归并
            merge(data,start,end);
        }
    }

    @Test
    public void testMergeSort(){
        int[] arr={1,2,4,3,2,1};
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
